<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>树和二叉树的转换</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="树和二叉树的转换">树和二叉树的转换</h1>
<h1 id="1-lc-431-encode-n-ary-tree-to-binary-tree">1. LC 431. Encode N-ary Tree to Binary Tree</h1>
<ul>
<li><a href="https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/">https://leetcode.com/problems/encode-n-ary-tree-to-binary-tree/</a></li>
</ul>
<p>Design an algorithm to encode an N-ary tree into a binary tree and decode the binary tree to get the original N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. Similarly, a binary tree is a rooted tree in which each node has no more than 2 children. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that an N-ary tree can be encoded to a binary tree and this binary tree can be decoded to the original N-nary tree structure.</p>
<p>Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See following example).</p>
<p>For example, you may encode the following 3-ary tree to a binary tree in this way:</p>
<pre><code><code><div>Input: root = [1,null,3,2,4,null,5,6]
Note that the above is just an example which might or might not work. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.


Constraints:

The height of the n-ary tree is less than or equal to 1000
The total number of nodes is between [0, 10^4]
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
</div></code></code></pre>
<p>具体转换建议看这里的介绍</p>
<ul>
<li><a href="https://jingyan.baidu.com/article/19020a0a743851529d28421a.html">https://jingyan.baidu.com/article/19020a0a743851529d28421a.html</a></li>
</ul>
<h2 id="将树转换为二叉树">将树转换为二叉树：</h2>
<p>树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：1.在所有兄弟结点之间加一连线2.对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。</p>
<p><img src="pics/tree1.jpg" alt="tree1.jpg"></p>
<h2 id="二叉树转换回树">二叉树转换回树</h2>
<p>是树转换为二叉树的逆过程。</p>
<p>1.加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。</p>
<p>2.去线。删除原二叉树中所有结点与其右孩子结点的连线。</p>
<p>如下图所示：</p>
<p><img src="pics/tree2.jpg" alt="tree2.jpg"></p>
<p>我的代码</p>
<pre><code class="language-python"><div><span class="hljs-string">"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""</span>

<span class="hljs-string">"""
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
"""</span>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Codec</span>:</span>
    <span class="hljs-comment"># Encodes an n-ary tree to a binary tree.</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">encode</span><span class="hljs-params">(self, root: <span class="hljs-string">'Node'</span>)</span> -&gt; TreeNode:</span>
        <span class="hljs-keyword">if</span> root == <span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>
        m = {}
        q = [root]
        <span class="hljs-keyword">while</span> q:
            node = q.pop(<span class="hljs-number">0</span>)
            <span class="hljs-keyword">if</span> node <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> m:
                m[node] = TreeNode(node.val)
                
            <span class="hljs-keyword">if</span> node.children:
                child1 = node.children[<span class="hljs-number">0</span>]
                m[child1] = TreeNode(child1.val)
                m[node].left = m[child1]
                pre = m[child1]
                q.append(child1)
                
                <span class="hljs-keyword">for</span> child <span class="hljs-keyword">in</span> node.children[<span class="hljs-number">1</span>:]:
                    m[child] = TreeNode(child.val)
                    pre.right = m[child]
                    pre = m[child]
                    q.append(child)
        <span class="hljs-comment">#self.pre(m[root])</span>
        <span class="hljs-keyword">return</span> m[root]
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pre</span><span class="hljs-params">(self, node)</span>:</span>
        <span class="hljs-keyword">if</span> node == <span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span>
        lv = node.left.val <span class="hljs-keyword">if</span> node.left <span class="hljs-keyword">else</span> <span class="hljs-string">"None"</span>
        rv = node.right.val <span class="hljs-keyword">if</span> node.right <span class="hljs-keyword">else</span> <span class="hljs-string">"None"</span>
        print(<span class="hljs-string">f"val <span class="hljs-subst">{node.val}</span> left:<span class="hljs-subst">{lv}</span> right:<span class="hljs-subst">{rv}</span>"</span>)
        self.pre(node.left)
        self.pre(node.right)
    
    
	<span class="hljs-comment"># Decodes your binary tree to an n-ary tree.</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">decode</span><span class="hljs-params">(self, data: TreeNode)</span> -&gt; 'Node':</span>
        <span class="hljs-keyword">if</span> data == <span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>
        m = {}
        q = [data]
        <span class="hljs-keyword">while</span> q:
            node = q.pop(<span class="hljs-number">0</span>)
            <span class="hljs-keyword">if</span> node <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> m:
                m[node] = Node(node.val, [])
            <span class="hljs-keyword">if</span> node.left:
                t = node.left
                m[t] = Node(t.val, [])
                m[node].children.append(m[t])
                <span class="hljs-keyword">while</span> t.right:
                    t = t.right
                    m[t] = Node(t.val, [])
                    m[node].children.append(m[t])
                q.append(node.left)
            <span class="hljs-keyword">if</span> node.right:
                q.append(node.right)
        <span class="hljs-keyword">return</span> m[data]
            
        
        

<span class="hljs-comment"># Your Codec object will be instantiated and called as such:</span>
<span class="hljs-comment"># codec = Codec()</span>
<span class="hljs-comment"># codec.decode(codec.encode(root))</span>
</div></code></pre>
<p>官方答案</p>
<pre><code class="language-python"><div><span class="hljs-string">"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""</span>
<span class="hljs-string">"""
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
"""</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Codec</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">encode</span><span class="hljs-params">(self, root)</span>:</span>
        <span class="hljs-string">"""Encodes an n-ary tree to a binary tree.
        :type root: Node
        :rtype: TreeNode
        """</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>

        rootNode = TreeNode(root.val)
        queue = deque([(rootNode, root)])

        <span class="hljs-keyword">while</span> queue:
            parent, curr = queue.popleft()
            prevBNode = <span class="hljs-literal">None</span>
            headBNode = <span class="hljs-literal">None</span>
            <span class="hljs-comment"># traverse each child one by one</span>
            <span class="hljs-keyword">for</span> child <span class="hljs-keyword">in</span> curr.children:
                newBNode = TreeNode(child.val)
                <span class="hljs-keyword">if</span> prevBNode:
                    prevBNode.right = newBNode
                <span class="hljs-keyword">else</span>:
                    headBNode = newBNode
                prevBNode = newBNode
                queue.append((newBNode, child))

            <span class="hljs-comment"># use the first child in the left node of parent</span>
            parent.left = headBNode

        <span class="hljs-keyword">return</span> rootNode


    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">decode</span><span class="hljs-params">(self, data)</span>:</span>
        <span class="hljs-string">"""Decodes your binary tree to an n-ary tree.
        :type data: TreeNode
        :rtype: Node
        """</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> data:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>

        <span class="hljs-comment"># should set the default value to [] rather than None,</span>
        <span class="hljs-comment"># otherwise it wont pass the test cases.</span>
        rootNode = Node(data.val, [])

        queue = deque([(rootNode, data)])

        <span class="hljs-keyword">while</span> queue:
            parent, curr = queue.popleft()

            firstChild = curr.left
            sibling = firstChild

            <span class="hljs-keyword">while</span> sibling:
                <span class="hljs-comment"># Note: the initial value of the children list should not be None, which is assumed by the online judge.</span>
                newNode = Node(sibling.val, [])
                parent.children.append(newNode)
                queue.append((newNode, sibling))
                sibling = sibling.right

        <span class="hljs-keyword">return</span> rootNode
</div></code></pre>

    </body>
    </html>